1. Field of the Invention
This invention relates to transmission of digital information. More particularly, this invention relates to operations in the routing of packets in data switching networks.
2. Description of the Related Art
The meanings of certain acronyms and abbreviations used herein are given in Table 1.
TABLE 1Acronyms and AbbreviationsBSTBinary Search TreeDIPDestination Internet Protocol AddressDRAMDynamic Random Access MemoryHCAHost Channel AdapterIPInternet ProtocolLPMLongest Prefix MatchMSBMost Signficant BitsNICNetwork Interface CardRIFRouter InterfaceSRAMStatic Random Access MemoryTCAMTernary Content Addressable Memory
Modern internet routers determine data routing based on searching for a packet destination IP address (DIP) in a database of forwarding information known as a routing table. The routing table, rather than storing a full DIP, stores only some of the leading portion, known as a prefix. The prefix comprises some number of the most significant bits of the DIP. The remaining bits are treated as “don't care” bits for purpose of a DIP search in the routing table. Computers that belong to a subnetwork are addressed by a common prefix in their IP address.
The most specific of the matching table entries—the one with the longest subnet mask—is called the longest prefix match (LPM). This is the entry in the routing table in which the largest number of leading address bits of the destination address match those in the table entry. This entry is selected to route the packet.
Searching the routing table for the LPM is a bottleneck in routing throughput. Implementing LPM is challenging as the destination IP (DIP) of each incoming packet has to be compared against the entries of the routing table, which can be very large, for example more than 500k entries, to find the best (longest) prefix match. Various hardware-based solutions have been proposed. However, the circuitry required to implement such solutions becomes complex. Moreover, the increasing amount of internet traffic and demands for reduced latency have resulted in relatively costly router circuitry having high power consumption and heat dissipation.
One method that implements a longest prefix match in a routing table involves constructing a binary search tree on prefix lengths with markers, as proposed in the document Scalable High-Speed Prefix Matching, Waldvogel et al (1997), in Proceedings of the ACM SIGCOMM '97 conference on applications, technologies, architectures, and protocols for computer communication, pp 25-36, which is herein incorporated by reference. It can determine the LPM in a worst case of five hash lookups for IPv4 and of seven for IPv6. The method requires addition of new entries called markers in the tree to ensure that the correct result is obtained for all the packets. When there is a match on a given node of the tree, that information can be used to narrow down the search. Moreover, on a match, the tree is mutated to a new tree that takes into account the information provided by the match. Although the mutation is optimal to reduce the number of accesses to complete the search, it is complex to implement in hardware.